This invention relates to compressing and decompressing program code and data in a computer system, particularly in a read only memory device and the main memory of an embedded computer system.
Appended to the detailed description is Appendix A, which contains C language, source code files, which make up compression and decompression algorithms. The source code is subject to copyright protection. The copyright owner, Digital Equipment Corporation, has no objection to the reproduction of the patent document, containing Appendix A, as it appears in the Patent and Trademark Office Patent file or records. Excepting only this limited reproduction right, the copyright owner expressly reserves all other copyright rights whatsoever.
Computer systems typically implement a memory hierarchy, having a main electronic (RAM) memory which is augmented by different forms of mass storage. During processing operations, main memory commonly holds the program code and data which is accessed by the central processing unit (CPU) for processing. Auxiliary, mass storage devices, such as magnetic disks, magnetic tapes, optical disks, read only memory (ROM) storage devices, or a network node, contain additional information which is transferred into main memory as needed by the CPU. Since the capacities of such auxiliary storage devices substantially exceed the capacity of main memory, many modern computer systems include some type of virtual memory system.
Through the implementation of virtual memory and demand paging, portions of program code and data stored in the auxiliary storage can be retrieved into main memory so that it can be processed by the CPU as needed. In such a system, not only is data periodically transmitted to main memory by auxiliary storage, but also main memory will periodically have to update auxiliary storage in the event that specific data has been modified by the CPU during processing operations and main memory consequently contains the only correct version of the data.
Unlike the computer system discussed above, in which main memory and auxiliary storage are very regularly exchanging data, a so-called xe2x80x9cembedded systemxe2x80x9d has a main memory which operates more independently. In an embedded system the main memory is typically loaded at the commencement of processing operations with program code and data from either a network or auxiliary storage. Thereafter, the CPU processes the data in main memory, but typically does not transmit data back from the main memory to some auxiliary storage device, or some other node on a connected network.
The efficient use of space in any storage medium is a highly desirable objective. Typically the greatest premium is placed on the efficient use of storage space in main memory, given that the electronic RAM""s which comprise main memory are the most costly storage device in a memory hierarchy, relatively speaking. Therefore, the need for efficient use of storage space is especially important in embedded systems given that their main memories tend to operate without support from auxiliary storage after initial loading. What is needed therefore is an approach to storage of data in computer systems, especially embedded computer systems, which improves the use of available storage space in the various storage devices.
In one embodiment of the invention, an apparatus for processing data includes a memory device, such as a main memory, for storing decompressed data, which is directly accessible to a CPU. The apparatus further includes another memory means in which data is stored in a compressed format, which is not directly accessible to the CPU. In order to access data the CPU transmits a virtual address which is subsequently translated into the physical address by which the virtual memory system determines if the requested data is present in the accessible portion of main memory.
If it is not, then the virtual memory system will transfer data from the compressed data storage device to the decompressed portion of main memory. In order to do so, the apparatus includes a means for decompressing the compressed data when it is transferred.
In yet other embodiments of the invention, when data is paged out of the decompressed portion of main memory it is compressed before it is stored in the storage device containing compressed data. Still further embodiments of the invention include the method by which data is compressed and decompressed in connection with a demand paging or a page out operation by the virtual memory.
By providing the compression and decompression of data in connection with a virtual memory system, this invention addresses the above discussed problems by providing an efficient means for storing data, particularly data stored in the main memory of an embedded computer system.
Given that this description only briefly summarizes the invention, a more complete understanding of the invention, as well as its objects, features, and advantages will be appreciated upon consideration of the detailed description of the preferred embodiment, presented in conjunction with the accompanying drawings, and the claims.